Networks may be classified according to whether the nodes are linked to one another using point-to-point connections or by a broadcast channel. In point-to-point networks, there are many links with each link connecting a single pair of nodes. Nodes sharing a point-to-point link may transmit directly to one another and nodes that do not share a point-to-point link may communicate by sending their message via one or more intermediate nodes. In broadcast networks, all of the nodes are linked together and share a single communication channel over which all messages are broadcast. Each broadcast message typically includes an address, which identifies the intended recipient. When a node receives a message, it checks the address to see if it is the intended recipient and if the message is for the receiving node, it processes the message. If the message is addressed to another node, the receiving node discards the message. An inherent problem in many broadcast networks is channel allocation, i.e., determining which node gets access to the communication channel when two or more nodes want to use it at the same time.
Two methods that have been used in protocols that address the channel allocation problem are “carrier sense” and “collision detection.” If a node is able to detect whether the channel is in use, it is said that the node is able to carrier sense. For a node to be able to carrier sense it must be able to receive the transmissions of every other node in the network. If two nodes simultaneously transmit a message on the shared channel, both messages will be distorted and neither understood. This is referred to as a “collision.” Like carrier sense, for a node to be capable of collision detection it must be able to receive the transmissions of every other node in the network.
The scale of a broadcast network is important for determining whether the carrier sense and collision detection methods can be used to solve the channel access problem. A home network consists of nodes that are relatively close together, generally being spaced apart by less than a meter to a few dozen meters. In a local area network (“LAN”), nodes may be separated by distances up to a few kilometers. The nodes in a wide area network (“WAN”) may be separated by thousands of kilometers. If the maximum distance between the nodes in a broadcast network is relatively small, the amount of signal attenuation is also generally small so that each node is able to receive the transmissions of all nodes in the network. In addition, the propagation time for a signal to reach the most distant node in the network is also relatively small, fixed, and known ahead of time. Thus, it is possible and practical to design a small scale broadcast network, such as a home network or a LAN, that is capable of carrier sensing and collision detection.
To implement collision detection, a sending node may listen for a collision while it transmits a message and for a predetermined short fixed time thereafter. If the sending node does not detect a collision within the time period, the node can assume that its message did not collide with another transmission. It may be impractical or difficult, however, to listen for collisions. In these circumstances, a sending node may infer that a collision occurred if it does not receive an acknowledgment from the receiving node within a predetermined time period after it sends a message.
Generally, transmission media may be wired or wireless. Copper wire and fibre optic cable are examples of wired media. The earth's atmosphere used by radio transmissions is an example of wireless media. A particular transmission media may be capable of carrying more than one communication channel. For instance, radio transmissions generally use a relatively narrow frequency band as a single communication channel.
Whether carrier sense and collision detection are possible depends on both the scale of the network and the type of transmission media used. If all of the nodes of a small scale, wired broadcast network are provided with enough transmit power so that a sending node's transmissions can be received by every node in the network, it has been generally assumed that all of the nodes can be provided with carrier sense and collision detection capabilities. In addition, it has been assumed that the nodes of such a network may be provided with collision avoidance capabilities, which are described below. These assumptions are generally not made, however, in a wireless network. Every node in a wireless network may not be within range of a transmitting node. Further, even if a transmitter uses sufficient power to reach every node in the network under dry atmospheric conditions, radio waves may be absorbed during rainy conditions. Moreover, in wireless networks the nodes are frequently mobile and nodes may be moved to positions where terrain blocks radio reception. In addition, wireless transmissions may be interfered with by other radio transmissions, both natural and man-made. Thus, protocols which rely on carrier sense and collision detection are typically not employed in wireless networks.
A number of communication protocols have been developed for use in broadcast networks. According to one early protocol, which employed only collision detection, whenever a node needed to send a message, it simply transmitted the message. The sending node listened to the channel and if a collision was detected, the sender waited a random time and then re-sent the message. In the case of a collision, if each of the two senders were to wait the same time period, the re-sent messages would again collide. Thus, by having each node wait a random time, the problem of simultaneous re-transmission is minimized. A network using this protocol is, however, very inefficient for a great deal of time is spent waiting and re-transmitting messages as a result of frequent collisions. The efficiency of the protocol can be improved by requiring that nodes send messages only at the start of periodic time intervals or “time slots,” but a great deal of time is still wasted.
With the early protocol described above, the nodes do not check to see if the channel is in use before sending a message. In another protocol, referred to as Carrier Sense Multiple Access (“CSMA”), the nodes first listen (carrier sense) to see if the channel is in use before transmitting. If the channel is not in use, the node sends its message. If the channel is in use, the node waits until the channel is idle and then transmits its message.
A problem with the CSMA protocol is that collisions can still occur. A node can sense that the network is idle and start sending a message only to discover that another node began transmitting on the channel at the same time or just before it started sending its message. The Carrier Sense Multiple Access with Collision Detection (“CSMA/CD”) protocol improves on the CSMA protocol by requiring nodes to immediately stop transmitting when they detect a collision. After collision detection, each node waits a random time before again attempting to transmit. The CSMA/CD protocol is widely used in wired LANs, such as Ethernet.
Other types of protocols solve the multiple access problem by attempting to avoid collisions altogether. In protocols using collision avoidance, the time period during which a node is transmitting on the channel may be referred to as a “transmission period” and the period between transmission may be called a “contention period.” In one type of collision-free protocol known as the Basic Bit-Map protocol, the contention period is divided into N time slots, where N is the number of nodes that belong to the network. Each node is assigned one of the time slots and if a node has a message ready to transmit, it sends a bit during its time slot to reserve a transmission period on the channel. At the end of the contention period, those nodes having a message to send take turns sending their messages in the same sequence as their respective time slot positions.
One problem with the protocols that use carrier sense, collision detection, or collision avoidance is the limited bandwidth provided by the single communication channel. Even if the channel is used efficiently to maximize transmit time and minimize contention periods, as it is with CSMA/CD, it remains a problem that only one node may transmit at a time so there is still a substantial amount of time during which many of the nodes of the network cannot carry on communications. Where nodes interact frequently with many different nodes, the use of these protocols significantly degrades network performance.
As explained above, the nodes in wireless networks are generally unable to consistently perform carrier sensing and collision detection. For this reason, protocols used in wireless networks generally adopt multiple access techniques that are fundamentally different from the carrier sensing protocols described above. Wireless networks typically address the channel allocation problem by dividing or multiplexing the channel in some way. In addition, the protocols typically used in wireless networks can increase the amount of communication bandwidth available. In Frequency Division Multiple Access (“FDMA”), the available frequency spectrum is divided into frequency bands and each pair of nodes that needs to communicate is assigned the exclusive use of a band. In Time Division Multiple Access (“TDMA”), a fixed time period is divided into time slots and each node is assigned the exclusive use of one of the time slots for sending messages. In Code Division Multiple Access (“CDMA”), nodes are assigned a distinct code waveform (taken from a set of orthogonal waveforms) that is used to modulate a carrier wave. Decoders in receiver nodes use the assigned code waveform to demodulate the received waveform.
The Spatial Division Multiple Access (“SDMA”) method is used in a particular type of wireless network: the cellular telephone network. Typically, cellular telephone networks have a number of cells with a central base station at a fixed location at the center of each cell. At any point in time, a number of mobile nodes may be distributed geographically within the cell. Cellular networks typically use SDMA in conjunction with some combination of FDMA, CDMA, or TDMA. Commonly, FDMA is used to assign one or more frequency bands as “control channels” that are reserved for the base station to send and receive requests from the mobile nodes. The base station uses the control channel to assign the remaining frequency bands (and time slots or waveform codes) for temporary use by the particular nodes currently within the cell. Adjacent cells typically do not use the same frequency bands.
The base station assigns the same frequency band to two geographically separated nodes that cannot sense one another's transmissions when SDMA is employed. For example, two nodes that are located at opposite sides of a cell may be out of range of one another and thus each node can use the same frequency band without interfering with the other. Through the simultaneous use of the same frequency band, SDMA increases the communications bandwidth of the network. However, SDMA requires the use of phased array antennae at the base station that can direct radio transmissions in a particular direction. The base station uses its ability to transmit directionally to send a message to a node at a particular location and away from the other node using the same frequency band. In addition, SDMA relies on the ability of a central base station to determine when SDMA is possible and to allocate frequency bands, time slots, or code waveforms.
In summary, broadcast networks generally need a method for allocating channel access among nodes. Protocols employing carrier sense, collision detection, and collision avoidance methods are typically used in small scale wired, networks. CSMA/CD is an access method that is commonly used in wired networks. One problem facing wired networks is the limited communication bandwidth provided by a single channel. As a result, there is a need for increased bandwidth wired broadcast networks. Wireless networks generally employ FDMA, TDMA, or CDMA protocols. In addition, SDMA is used in cellular telephone networks. FDMA, TDMA, CDMA, and SDMA protocols can increase the bandwidth available for communication. However, as implemented in cellular telephone networks, SDMA requires a central base station with a phased array antennae and nodes that are spatially separate from one another. Thus, SDMA does not appear to be adaptable for use in a wired network for increasing the communication bandwidth of the network.
Accordingly, there is a need for a method and apparatus that can provide increased bandwidth in a wired broadcast network.